﻿using System;
using System.Linq;

namespace AlgorithmPractice;

/// <summary>
/// 使用函数的递归（嵌套）调用，实现归并排序（从小到大）
/// </summary>
public class MergeSort
{
    public static void Sort(int[] toBeSorted)
    {
        var sorted = StartSort(toBeSorted);
        Console.WriteLine(string.Join(",", sorted));
    }

    /// <summary>
    /// 开始排序
    /// </summary>
    /// <param name="toBeSorted">等待排序的数组</param>
    /// <returns>排序后的数组</returns>
    private static int[] StartSort(int[] toBeSorted)
    {
        if (!toBeSorted.Any())
        {
            return Array.Empty<int>();
        }

        //如果分解到只剩一个数，返回该数
        if (toBeSorted.Length == 1)
        {
            return toBeSorted;
        }

        //将数组分解成左右两半
        var mid = toBeSorted.Length / 2;
        var left = toBeSorted[0..mid];
        var right = toBeSorted[mid..];

        //嵌套调用，对两半分别进行排序
        left = StartSort(left);
        right = StartSort(right);

        //合并排序后的两半
        var merger = Merger(left, right);

        return merger;
    }

    /// <summary>
    /// 合并两个已经排序完毕的数组（从小到大）
    /// </summary>
    /// <param name="a">第一个数组</param>
    /// <param name="b">第二个数组</param>
    /// <returns>合并后的数组</returns>
    private static int[] Merger(int[] a, int[] b)
    {
        var m = new int[a.Length + b.Length];

        int mi = 0, ai = 0, bi = 0;

        //轮流从两个数组中取出较小的值，放入合并后的数组中
        while (ai < a.Length && bi < b.Length)
        {
            if (a[ai] <= b[bi])
            {
                m[mi] = a[ai];
                ai++;
            }
            else
            {
                m[mi] = b[bi];
                bi++;
            }

            mi++;
        }

        //将某个数组内剩余的数字放入合并后的数组中
        if (ai < a.Length)
        {
            for (var i = ai; i < a.Length; i++)
            {
                m[mi] = a[i];
                mi++;
            }
        }
        else
        {
            for (var i = bi; i < b.Length; i++)
            {
                m[mi] = b[i];
                mi++;
            }
        }

        return m;
    }
}